An operating system (OS) is a collection of software that manages computer hardware resources and provides common services for computer programs. The operating system is an essential component of the system software in a computer system. Application programs usually require an operating system to function. Amongst many functionalities of an operating system, scheduling is the method by which threads, processes or data flows are given access to system resources (e.g. processor time, communications bandwidth). This is usually done to load balance and share system resources effectively or achieve a target quality of service.
The need for a scheduling algorithm arises from the requirement for most modern systems to perform multitasking (executing more than one process at a time) and multiplexing (transmit multiple data streams simultaneously across a single physical channel). A scheduler of an operating system is concerned mainly with throughput (e.g., the total number of processes that complete their execution per time unit), latency (e.g., turnaround time-total time between submission of a process and its completion), response time (e.g., amount of time it takes from when a request was submitted until the first response is produced), fairness (e.g., equal central processing unit or CPU time to each process, or more generally appropriate times according to each process' priority and workload), and waiting time (e.g., the time the process remains in the ready queue). In practice, these goals often conflict (e.g. throughput versus latency), thus a scheduler of an operating system may implement a suitable compromise. Preference is given to any one of the above mentioned concerns depending upon the user's needs and objectives.
FIG. 1 is a block diagram illustrating a conventional task scheduling process of an operating system. Referring to FIG. 1, system 100 includes processing resources 102 as hardware resources, such as multiple processor cores 103-104 for executing multiple processes concurrently. The processes may be scheduled by scheduler 101 of an operating system using various scheduling algorithms and dispatched to processing resources 102 for execution. In this example, typically, the processes that are ready to be executed are buffered in process queue 105. Process queue 105 includes multiple entries 111-113, each corresponding one of the priorities. Each of entries 111-113 is linked with or referenced to a list of threads such as lists of threads 121-123 of different processes.
In this example, list 121 includes multiple threads 131-135 associated with processes A and process B. When a signal is received indicating that there is a process resource available, scheduler 101 walks through process queue 105 to identify an entry that is not empty and has the highest priority amongst the entries 111-113 (in this example for the purpose of illustration, priority 1 is higher than priority 2, which is higher than priority 3, and so on). In this example, scheduler 101 locates entry 111 that is not empty (e.g., with the highest priority) and retrieves list 121 of threads 131-135, where threads 131-135 have been enqueued at the tail of list 121 and dequeued at the head of list 121.
In this example, it is assumed thread 131 is dispatched for execution. When the execution of thread 131 has been completed or self-suspended, scheduler 101 will walk through process queue 105 again and find another thread for execution. In this situation, thread 132 is identified and dispatched. Since there are several threads 132-134 associated with process B before reaching thread 135 of process A in list 121, significant more threads of process B may be executed compared to process A (e.g., thread 135). As a result, the execution of threads 132-134 of process B may starve the execution of threads for process A. This will be “unfair” to process A and it may cause software decay of process A in a multi-threading system, in which a process is entitled to fair time slots for executing its associated threads.